package 剑指offer;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:39:43 
* @Description：
* 
输入一个链表，输出该链表中倒数第k个结点。
*/

public class A14链表当中倒数第K个结点 {
	//定义链表结构
	
	
	//快慢指针的运用
	/*
	 * （1）第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；
　　（2）从第k步开始，第二个指针也开始从链表的头指针开始遍历；
　　（3）由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
	 */
	public  static ListNode FindKthToTail(ListNode head,int k) {
		if (head==null || k<=0) {
			return null;
		}
		ListNode p,target;
		p=head;                             //p就是快指针，先跑k个
		target=head;
		int i=0;
		while (p!=null) {
			if (i>=k) {
				target=target.next;        //target为慢指针，在p.next==null，即整个链表跑到头时，这时target恰好在倒数第k个结点上面
			}
			p=p.next;
			i++;
		}
		if (i<k) {
			return null;
		}
		return target;
	}
	
	public static ListNode init(){
        Scanner scan=new Scanner(System.in);
        String[] array=scan.nextLine().split(" ");
        ListNode pHead=new ListNode(Integer.parseInt(array[0]));
        ListNode walkNode=pHead;
        for(int i=1;i<array.length;i++){
            ListNode newNode=new ListNode(Integer.parseInt(array[i]));
            walkNode.next=newNode;
            walkNode=newNode;
        }
        return pHead;
    }
	
	
	/*
7
1 4 6 7 8 0 3
5

6
	 */
    public static void main(String[]args){
        Scanner scan=new Scanner(System.in); 
        int n=scan.nextInt();    
        ListNode pHead=init();
        int k=scan.nextInt();
        System.out.println(FindKthToTail(pHead, k));              //注意对比
        System.out.println(FindKthToTail(pHead, k).val);
    }


}
